package UseBfHamitonCycle;

import java.util.*;

public class HamiltonianCycle {
    private int[][] graph; // 图的邻接矩阵
    private boolean[] visited; // 记录节点是否已访问
    private List<Integer> path; // 记录当前路径
    private int start; // 起点

    //初始化图、访问数组、路径列表和起点start
    public HamiltonianCycle(int[][] graph) {
        this.graph = graph;
        visited = new boolean[graph.length];
        path = new ArrayList<>();
        start = 0; // 假设起点为0
    }
    //寻找哈密顿回路
    public void findHamiltonianCycle() {
        visited[start] = true;// 将起点标记为已访问
        path.add(start); // 将起点添加到路径列表中
        dfs(start, 1);// 开始进行深度优先搜索
        visited[start] = false;// 将起点标记为未访问，以便下一次搜索时重新使用它
        path.remove(path.size() - 1);// 从路径列表中移除起点

    }

    private void dfs(int node, int count) {//进行深度优先搜索
        if (count == graph.length && graph[node][start] == 1) { // 找到哈密顿回路
            System.out.println(path); // 输出路径
            return;
        }
        for (int i = 0; i < graph.length; i++) {
            if (!visited[i] && graph[node][i] == 1) {// 如果该节点未被访问且与当前节点存在路径，则继续搜索
                visited[i] = true;// 将该节点标记为已访问
                path.add(i);// 将该节点添加到路径列表中
                dfs(i, count + 1);//递归调用dfs,继续进行深度优先搜索
                visited[i] = false;// 将该节点标记为未访问，以便下一次搜索时重新使用它
                path.remove(path.size() - 1);// 从路径列表中移除该节点
            }
        }
    }

    public static void main(String[] args) {
        int[][] graph = {{0, 1, 1, 0},
                {1, 0, 1, 1},
                {1, 1, 0, 1},
                {0, 1, 1, 0}};
        HamiltonianCycle hc = new HamiltonianCycle(graph);
        hc.findHamiltonianCycle();
    }
}

